package net.tp.algo.graph.shortestpath;

import net.tp.algo.graph.Graph;
import net.tp.algo.graph.Graph.Edge;

import java.util.*;

/**
 *
 * <p>Bellman-Ford algorithm for shortest path.</p>
 *
 *
 *
 *
 * @author Trung Phan
 *
 */
public class BellmanFord {

    private final double[] distanceTo;
    private final int[] edgeTo;
    private final int source;

    private final boolean hasNegCycle;

    /**
     *
     * @param graph directed weighted graph
     * @param source source node
     */
    public BellmanFord(Graph graph, int source) {

        this.source = source;

        int N = graph.order();

        this.distanceTo = new double[N];
        Arrays.fill(this.distanceTo, Double.MAX_VALUE);

        this.edgeTo = new int[N];
        Arrays.fill(edgeTo, -1);

        this.distanceTo[source] = 0;
        this.edgeTo[source] = source;
        boolean hasNegCycle = true;

        // iterate N-1 times to find shortest path, iterate 1 more round to detect negative cycle
        for (int i = 0; i < N; i++) {
            boolean changed = false;
            for (int u = 0; u < N; u++) {
                if (distanceTo[u] < Double.MAX_VALUE) {
                    for (Edge edge : graph.edges(u)) {
                        int w = edge.other(u);
                        if (distanceTo[w] > distanceTo[u] + edge.weight()) {
                            distanceTo[w] = distanceTo[u] + edge.weight();
                            edgeTo[w] = u;
                            changed = true;
                        }
                    }
                }
            }
            if (!changed) {
                hasNegCycle = false;
                break;
            }
        }

        this.hasNegCycle = hasNegCycle;

    }

    public boolean hasNegCycle() {
        return hasNegCycle;
    }

    public double distanceTo(int w) {
        if (hasNegCycle) {
            throw new IllegalArgumentException("Negative cycle detected.");
        }
        return distanceTo[w];
    }

    public List<Integer> pathTo(int w) {
        if (hasNegCycle) {
            throw new IllegalArgumentException("Negative cycle detected.");
        }

        if (distanceTo[w] == Double.MAX_VALUE) {
            return Collections.emptyList();
        }

        List<Integer> result = new LinkedList<>();
        for (; w != source; w = edgeTo[w]) {
            result.add(0, w);
        }
        result.add(0, source);

        return result;
    }

}
